package q30_findSubstring;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution {
    public static void main(String[] args) {
        String s = "barfoofoobarthefoobarman";
        String[] words = {"bar","foo","the"};
        System.out.println(findSubstring(s,words));

    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || words == null || words.length == 0) {
            return result;
        }

        // words中每个单词出现的次数
        Map<String, Integer> wordsMap = new HashMap<>();
        for (String word : words) {
            if (!s.contains(word)) {
                // 没有当前单词，直接返回
                return result;
            }
            wordsMap.put(word, wordsMap.getOrDefault(word, 0) + 1);
        }

        // 一个单词的长度
        int oneLen = words[0].length();
        // 需要搜索的总长度，即滑动窗口的大小
        int wordsLen = oneLen * words.length;
        if (s.length() < wordsLen) {
            // 主串长度小于搜索长度，直接返回
            return result;
        }

        // 只讨论从0,1...,oneLen-1开始的子串情况
        // 每次进行匹配的窗口大小为wordsLen，每次右移oneLen长度
        // 这样就能覆盖从所有位置开始的窗口
        for (int i = 0; i < oneLen; ++i) {
            int left = i;
            // 因为要使用substring，所以right最大可以达到s.length()
            int right = i;
            // 子串中单词出现的次数
            Map<String, Integer> subMap = new HashMap<>();
            // 右指针不能超过主串长度
            while (right + oneLen <= s.length()) {
                // 得到当前单词
                String word = s.substring(right, right + oneLen);
                // 右指针右移
                right += oneLen;
                // words中没有这个单词，当前窗口匹配失败，直接右移到这个单词后面重新匹配
                if (!wordsMap.containsKey(word)) {
                    left = right;
                    // 清空subMap，为重新匹配做准备
                    subMap.clear();
                } else {
                    // 当前单词出现的次数加1
                    subMap.put(word, subMap.getOrDefault(word, 0) + 1);
                    while (subMap.get(word) > wordsMap.get(word)) {
                        // 从子串map中删除最左侧单词，直至word次数不大于需要的次数
                        String del = s.substring(left, left + oneLen);
                        // 最左的单词肯定在子串map里，所以可以直接减1
                        subMap.put(del, subMap.get(del) - 1);
                        // 左指针右移一个单词
                        left += oneLen;
                    }
                    if (subMap.equals(wordsMap)) {
                        result.add(left);
                    }
                }
            }
        }

        return result;
    }
}
